Elliptic Curve Arithmetic Performance

Slides

Binary Fields

At one point there was a push to use fields where the group order was a power of 2, as these could be implemented more efficiently with [[CLMUL Instruction Set]] and even specific fields such as [[Koblitz Curves]].

However, these were eventually discarded and are no longer recommended for use as they are much easier to solve the Discrete Logarithm Problem in using Joux’s Updated Index Calculus Algorithm (if n is not prime) or using the Function Field Sieve otherwise.

Montgomery Curves

XZ Coordinates

Doubling

Can be done in only 2 multiplications and 2 squarings. dbl-1987-m-3

Adding

Can be done with only 4 multiplications and 2 squarings. mdadd-1987-m

Edwards Curves

Projective Coordinates

Doubling

3 multiplications, 4 squarings dbl-2007-bl

Addition

10M + 1 squaring. add-2007-bl

Inverted Coordinates

Doubling

3 multiplications, 4 squarings. dbl-2007-bl

Adding

9 multiplications, 1 squaring. add-2007-bl

Extended Coordinates

Doubling

4M + 4S dbl-2008-hwcd

Adding

9M add-2008-hwcd

References